package top.minuy.structure.graph.path.weighted;

import top.minuy.structure.graph.representations.table.WeightedGraph;

/**
 * Floyed 多源有权图最短路径算法
 *
 * @author Minuy
 * @time 20:18
 * @date 2021/11/26
 */
public class Floyed {
    private WeightedGraph g;
    private int[][] dis;
    private boolean hasNegativeCycle;

    public Floyed(WeightedGraph g) {
        this.g = g;

        // 初始化距离二维数组
        dis = new int[g.V()][g.V()];
        for (int i = 0; i < dis.length; i++) {
            for (int j = 0; j < dis[i].length; j++) {
                dis[i][j] = Integer.MAX_VALUE;
            }
        }

        // 根据图初始化距离数组
        for (int v = 0; v < g.V(); v++) {
            dis[v][v] = 0;
            for (int w : g.adj(v)) {
                dis[v][w] = g.getWeight(v, w);
            }
        }

        // Floyed 算法，判断v和w直接能不能经过某个点t得到权更少的路径
        for (int t = 0; t < g.V(); t++) {
            for (int v = 0; v < g.V(); v++) {
                for (int w = 0; w < g.V(); w++) {
                    if (dis[v][t] != Integer.MAX_VALUE && dis[t][w] != Integer.MAX_VALUE) {
                        int newDis = dis[v][t] + dis[t][w];
                        if (newDis < dis[v][w]) {
                            dis[v][w] = newDis;
                        }
                    }
                }
            }
        }

        // 检测负权环
        for (int v = 0; v < g.V(); v++) {
            if (dis[v][v] != 0) {
                hasNegativeCycle = true;
                return;
            }
        }

    }

    public boolean isConnectedTo(int s, int t) {
        g.validateVertex(s);
        g.validateVertex(t);

        return dis[s][t] != Integer.MAX_VALUE;
    }

    public boolean hasNegativeCycle() {
        return hasNegativeCycle;
    }

    public int disTo(int s, int t) {
        g.validateVertex(s);
        g.validateVertex(t);
        if (hasNegativeCycle()) {
            throw new RuntimeException("Graph has negative cycle.");
        }
        return dis[s][t];
    }

}
